package com.wuyou.mid;

/**
 * 33. 搜索旋转排序数组
 */
public class Search {

    public static void main(String[] args) {
//        int[] nums = {3, 5, 1};
//        int target = 5;
        int[] nums = {2, 3, 4, 5, 6, 7, 8, 9, 1};
        int target = 9;

        System.out.println(sol_2(nums, target));
    }

    /**
     * 二分
     *
     * @param nums
     * @param target
     * @return
     */
    public static int sol_2(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            // 二分
            int mid = (l + r) / 2;
            if (nums[mid] == target) {
                return mid;
                // mid - r 有序
            } else if (nums[mid] < nums[r]) {
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1;
                }
            } else {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
        }
        return -1;
    }


    // O(N)
    public static int sol_1(int[] nums, int target) {
        int l = 0, mid = nums.length / 2, r = nums.length - 1;
        while (true) {
            if (nums[l] == target) return l;
            if (nums[r] == target) return r;
            if (nums[l] < target) {
                l++;
            } else {
                mid = l;
                break;
            }
            if (nums[r] > target) {
                r--;
            } else {
                mid = r;
                break;
            }
        }
        if (mid == l) {
            while (mid <= r) {
                if (nums[mid] == target) return mid;
                mid++;
            }
        } else {
            while (mid >= l) {
                if (nums[mid] == target) return mid;
                mid--;
            }
        }
        return -1;
    }
}
